![]() |
The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817 Pub Date: 03/01/99 |
Previous | Table of Contents | Next |
The key schedule for Twofish is a really a huge piece by itself. While it reuses many of the components of the cipher, it also required a significant amount of independent engineering. This chapter addresses the issues we came across in designing the key schedule.
To understand the design of the key schedule, it is necessary to consider how key material is used in Twofish:
In this section, we discuss whether different sequences of subkeys can give equivalent encryption functions. Recall that F´ is the F function without the addition of the round subkeys, which takes two 32-bit words as input and produces two 32-bit words as output. For this analysis we keep the function F´ constant. That is, we only vary the subkeys Ki and not S.
The properties of a Feistel cipher ensure that no pair of 2-round subkey sequences can be equivalent for all inputs. It is natural to ask next whether any pairs of three sequential rounds subkeys can exist that cause exactly the same encryption.
For a pair of subkey sequences, (k0, k1, k2) and (k*0, k*1, k*2), to be equivalent in their effects, every input block (L0, R0) must encrypt to the same output block (L1, R2) for both sequences of subkeys. Note that k0 ≠ k*0 and k2 ≠ k*2, as we would otherwise have two sequences of 2-round keys that would define the same 2-round encryption function. We have the following equalities:
R1 = R0 ⊕ (k0 + F´(L0))
R*1 = R0 ⊕ (k*0 + F´(L0))
L1 = L0 ⊕ (k1 + F´(R1))
L1 = L0 ⊕ (k*1 + F´(R*1))
R2 = R1 ⊕ (k2 + F´(L1))
R2 = R*1 ⊕ (k*2 + F´(L1))
where ⊕ represents bitwise XORing, and + represents 32-bit componentwise addition. Using the two equations for L1 we get
k1 + F´(R1) = k*1 + F´(R*1)
δ1 = F´(R1) - F´(R*1)
where δ1 = k*1 - k1 is fixed. Let T = F´ (L0) + k0 and observe that when L0 goes over all possible values, so does T. We get
δ1 = F´(R0 ⊕ T) - F´(R0 ⊕ (T + δ0)) (8.1)
where δ0 = k*0 - k0. Note that δ1 and δ0 depend only on the round keys, and that the equation must hold for all values of R0 and T. Set T = 0 and look at the cases R0 = 0 and R0 = δ0. We get
F´(0) - F´(δ0) = δ1 = F´(δ0) - F´(0) = - δ1
The subtraction here is modulo 232 for each of the two 32-bit words. That leaves us with the following possible values for δ1:
δ1 ∈ {(0,0), (0,231), (231,0), (231,231)}
These are the possible difference values at the output of F´ in equation 8.1. We can easily convert them to difference values at the input of the PHT of F´. Each of the possible values for δ1 corresponds to exactly one possible value for (δT0, δT1):
(δT0, δT1) ∈ {(0,0), (0,231), (231,0), (231,231)}
We can write down the analogue to equation 8.1 for g:
δT0 = g(R´ ⊕ T´) - g(R´ ⊕ (T´ + δ´0))
for all R´ and T´ and where δ´0 is the appropriate half of δ0. Observe that for the specific values of δT0 that are possible, subtraction and XOR are the same. For T´ = 0 this translates in a simple differential equation
δT0 = g(R´) ⊕ g(R´ ⊕ δ´0)
for all R´. We know that g has only one perfect differential: 0 → 0, so we conclude that δ´0 = 0. Similarly, we can conclude that the other half of δ0 must also be zero, and thus δ0 = 0. This is a contradiction, as k0 ≠ k*0.
We conclude that there are no two sets of 3-round subkey sequences that result in the same encryption function.
A Conjecture about Equivalent Subkeys in Twofish. We believe that, for up to 16 rounds of Twofish, there are no pairs of round subkeys that (with the same F´ function) result in the same encryption function. There simply do not appear to be enough degrees of freedom in choosing the different subkeys to make pairs of equivalent subkey sequences in as few as 16 rounds. However, we have been unable to prove this.
Note that this conjecture does not hold for an arbitrary number of rounds. Any fixed round function is an element of the permutation group on 128-bit values S2128. The order of this group is (2128)! ≈ 22134, and the order of any group element must be a divisor of the order of the group. Thus, any round function when iterated (2128)! times, results in the identity mapping.1 For this number of rounds there are thus many equivalent round subkeys.
1In fact, this property holds for any bijective function, including the complete Twofish encryption and the AES block cipher (irrespective of which candidate is chosen).
Can two keys generate the same sequence of round subkeys? We have performed exhaustive tests to show this is not the case. To generate the same round subkeys, the two keys will have to generate the same set of Ai and Bi.
We observe that Ai = h(2ρi, Me), where the h function consists of applying the MDS matrix multiplication to the four values (y0, y1, y2, y3) obtained by running the value 2i through 1 + N/64 levels of q0 and q0, XORing with bytes from Me. Since the MDS matrix is non-singular, it is easily seen that to generate the same sequence of Ai values, the keys must generate the same sequence of values for y0, y1, y2 and y3.
Previous | Table of Contents | Next |